package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/21 19:28
 *
 *
 买卖股票的最好时机：
 1，贪心，策略：最小买入，最大卖出，买入在卖出前
 2,自己想的，dp(i-1)为前i-1个数中的最小值，然后股票卖出点是i，这样就保证了卖出在买入前
 */

public class Main6 {
    public int maxProfit (int[] prices) {
        // write code here
        int ans=0;
        int dp=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;++i){
            dp=Math.min(dp,prices[i]);
            ans=Math.max(ans,prices[i]-dp);
        }
        return ans;
    }
    /*
    public int maxProfit (int[] prices) {
        // write code here
        if(prices.length==0)return 0;
        int mn=100005,idmn=-1;
        int mx=-1,idmx=-1;
        int ans=0;
        for(int i=0;i<prices.length;++i){
            if(prices[i]<mn){
                mn=prices[i];
                idmn=i;
            }
            //注意  卖出股票的变化,只能在idmn之后
            if(prices[i]>mx||idmn>=idmx){
                mx=prices[i];
                idmx=i;
            }
            System.out.printf("(%d,%d)--(%d,%d)\n",idmn,mn,idmx,mx);
            if(idmn<idmx){
                ans=Math.max(ans,mx-mn);
            }
        }
        return ans;
    }
    */
}
